﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0046_MaxProfit : IAlgorithm
    {
        // 买卖股票的最佳时机

        // 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

        // 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

        // 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

        // 提示：
        //1 <= prices.length <= 10^5
        //0 <= prices[i] <= 10^4

        public void Test()
        {
            // 算法参数定义
            var prices = new int[] { 7, 3, 5, 1, 6, 4 };
            // 算法执行与打印
            Console.WriteLine(MaxProfit(prices));
        }

        // 算法
        // 双指针
        public int MaxProfit(int[] prices)
        {
            if (prices.Length == 1)
                return 0;
            int l = 0, mp = 0;
            for (int i = 1; i < prices.Length; i++)
            {
                if (prices[i] < prices[l])
                    l = i;
                if (prices[i] - prices[l] > mp)
                    mp = prices[i] - prices[l];
            }
            return mp;
        }

        // 动态规划，每天持有非持有的利润

        // 单调栈解决
    }
}
